from typing import List


class Solution:
    """
    方法：回溯算法
    Args:
        candidates: 候选数字列表
        target: 目标和
    Returns:
        List[List[int]]: 所有满足条件的组合列表
    Time: O(N^(T/M + 1))，其中N是候选数数量，T是目标值，M是最小候选数
    Space: O(T/M)，递归调用栈的深度
    """
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        ans = []
        path = []
        def backtrack(i: int, left: int) -> None:
            if left == 0:
                ans.append(path.copy())
                return
            if left < candidates[i]:
                return
            for j in range(i, len(candidates)):
                path.append(candidates[j])
                backtrack(j, left - candidates[j])
                path.pop()
        backtrack(0, target)
        return ans